import java.util.TreeSet;

/**
 * 220. 存在重复元素 III
 * https://leetcode-cn.com/problems/contains-duplicate-iii/
 */
public class Solutions_220 {
    public static void main(String[] args) {
//        int[] nums = {1, 2, 3, 1};
//        int k = 3, t = 0;  // output: true

//        int[] nums = {1, 0, 1, 1};
//        int k = 1, t = 2;  // output: true

//        int[] nums = {1, 5, 9, 1, 5, 9};
//        int k = 2, t = 3;  // output: false

//        int[] nums = {-1, 2147483647};
//        int k = 1, t = 2147483647;  // output: false

        int[] nums = {0, 2147483647};
        int k = 1, t = 2147483647;  // output: true

        boolean result = containsNearbyAlmostDuplicate(nums, k, t);
        System.out.println(result);
    }

    /**
     * 解题思路：TreeMap 实现
     * @param nums
     * @param k 距离
     * @param t 差值
     * @return
     */
    public static boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (nums == null) {
            return false;
        }
        // 使用 TreeMap 实现
        TreeSet<Integer> treeSet = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            // 得到大于等于 nums[i] 的最小数
            Integer nearNum1 = treeSet.ceiling(nums[i]);
            if (nearNum1 != null && Math.abs((long) nums[i] - (long) nearNum1) <= t) {
                return true;
            }
            // 得到小于等于 nums[i] 的最大数
            Integer nearNum2 = treeSet.floor(nums[i]);
            if (nearNum2 != null && Math.abs((long) nums[i] - (long) nearNum2) <= t) {
                return true;
            }
            treeSet.add(nums[i]);
            // 保证 treeMap 中的元素个数小于等于 k 个
            if (treeSet.size() > k) {
                int popNum = nums[i - k];
                treeSet.remove(popNum);
            }
        }
        return false;
    }
}
